
/**
 * @program: 力扣刷题
 * @description
 * @author: LiChong
 * @create: 2021-05-13 15:02
 **/

import pojo.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 力扣21题：
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * eg:  输入：l1 = [1,2,4], l2 = [1,3,4]
 *      输出：[1,1,2,3,4,4]
 */
public class Code21 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(-10);
        ListNode l2 = new ListNode(-7);
        ListNode listNode = mergeTwoLists3(l1, l2);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode=listNode.next;
        }




    }
    // 方法一
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1==null&&l2==null){
            return null;
        }
        if (l1==null||l2==null){
            return l1==null?l2:l1;
        }
        ListNode head = l2;
        ListNode curHead = l2;
        ListNode next =null;
        while (l1!=null){
            next =l1.next;
           curHead = head;
           head = insertNodeToList(head,l1);
           if (head==null){
               ListNode theLastNode = findTheLastNode(curHead);
               theLastNode.next = l1;
               head = curHead;
               return head;
           }
            l1=next;
        }
        return head;

    }
    public static ListNode findTheLastNode(ListNode head){
        if (head==null){
            return null;
        }
        while (head.next!=null){
            head = head.next;
        }
        return head;

    }
    public static ListNode insertNodeToList(ListNode head,ListNode node){
        if (node.val<head.val){
            node.next = head;
            head = node;
            return head;
        }
        ListNode next;
        ListNode res=head;
        while(head!=null){
            next = head.next;
            if (next!=null){
            if (head.val<=node.val&&node.val<=next.val){
                head.next = node;
                node.next = next;
                break;
            }}
            head=head.next;
        }
        if (head==null){
            return null;
        }
        return res;
    }
    // 方法二，递归
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2){
        if(l1==null||l2==null){
            return l1==null?l2:l1;
        }
        if (l1.val>=l2.val){
           l2.next = mergeTwoLists2(l1,l2.next);
           return l2;
        }else {
            l1.next = mergeTwoLists2(l1.next,l2);
            return l1;
        }

    }
    public static class ListNodeCompare implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val-o2.val;
        }
    }
    /**
     * 使用优先级队列,其底层内存结构是顶堆
     */
    public static ListNode mergeTwoLists3(ListNode l1,ListNode l2){
        PriorityQueue<ListNode> queue = new PriorityQueue(new ListNodeCompare());
        if(l1!=null){
            queue.add(l1);
        }
        if(l2!=null){
            queue.add(l2);
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(queue.peek()!=null){
                cur.next = queue.poll();
                if (cur.next.next==null){
                    cur = cur.next;
                    continue;
                }
                queue.add(cur.next.next);
                cur = cur.next;
            }
        return dummy.next;
    }

}
